package com.cyh.pangu.offer;

/**
 * @author cuiyh9
 * @date 2020/8/26
 */
public class Offer04 {

    public boolean findNumberIn2DArray(int[][] matrix, int target) {
        int matrixHeigh = matrix.length;
        if (matrixHeigh == 0) {
            return false;
        }
        int matrixWidth = matrix[0].length;
        if (matrixWidth == 0) {
            return false;
        }
        int endHeight = 0;
        int endWidth = matrixWidth - 1;

        while (endHeight < matrixHeigh && endWidth >= 0) {
            if (matrix[endHeight][endWidth]  == target) {
                return true;
            } else if (matrix[endHeight][endWidth] < target) {
                endHeight ++;
            } else if (matrix[endHeight][endWidth] > target) {
                endWidth -- ;
            }
        }
        return false;
    }

    public static void main(String[] args) {
        Offer04 offer04 = new Offer04();
        int[][] aa = new int[][]{{1,4,7,11,15},{2,5,8,12,19},{3,6,9,16,22},{10,13,14,17,24},{18,21,23,26,30}};
        boolean result = offer04.findNumberIn2DArray(aa, 3);
        System.out.println("1:" + result);

        aa = new int[][]{{-1,3}};
        result = offer04.findNumberIn2DArray(aa, 3);
        System.out.println("1:" + result);


        aa = new int[][]{{2,5},{2,8},{7,9},{7,11},{9,11}};
        result = offer04.findNumberIn2DArray(aa, 7);
        System.out.println("2:" + result);

        aa = new int[][]{{-5}};
        result = offer04.findNumberIn2DArray(aa, -10);
        System.out.println("3:" + result);

    }
}
